package leetcode.L74;

import java.lang.reflect.GenericDeclaration;



class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        //获取每一行头尾的数
        int index = binarySearchColumn(matrix, target);
        if (index<0) {
            return false;
        }
        return binarySearchRow(matrix[index],target);
    }

    public int binarySearchColumn(int[][] matrix, int target) {
        //找到一个target>=的index
        int start=-1;
        int end = matrix.length - 1;
        int mid;
        while (start <= end) {
            mid = (end - start + 1) / 2 + start;
            if (matrix[mid][0] <= target) {
                start = mid;//因为Start这里已经有了+1上面
            } else {
                end=mid-1;
            }
        }
        return start;
    }

    public boolean binarySearchRow(int[] row, int target) {
        int low = 0, high = row.length - 1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            if (row[mid] == target) {
                return true;
            } else if (row[mid] > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return false;
    }
}